/*
题目描述：在O(1)时间内删除链表结点
方法：
1.找到待删除节点的前一个结点 O(n)
2.将待删除节点的下一个节点复制给待删除节点，然后删除待删除节点的下一个节点
如果假定待删除节点位于链表中，那么时间复杂度可以达到 O(1)
 */
public class E18_1 {
    public static void main(String[] args) {
        ListNode pListHead = new ListNode(1);
        pListHead.next = new ListNode(2);
        pListHead.next.next = new ListNode(3);
        pListHead.next.next.next = new ListNode(4);
        pListHead.next.next.next.next = new ListNode(5);

        DeleteNode(pListHead, pListHead.next.next);

        PrintListNode(pListHead);
    }

    public static void DeleteNode(ListNode pListHead, ListNode pToBtDeleted){
        if(pListHead == null || pToBtDeleted == null){
            return;
        }
        //被删除节点不是尾节点
        if(pToBtDeleted.next != null){
            ListNode pNext = pToBtDeleted.next;
            pToBtDeleted.value = pNext.value;
            pToBtDeleted.next = pNext.next;
            pNext = null;
        }
        //链表中只有一个节点，删除头结点
        else if(pListHead == pToBtDeleted){
            pListHead = null;
            pToBtDeleted = null;
        }
        //是尾节点，遍历一遍找到前节点
        else{
            ListNode node = pListHead;
            while(node.next != pToBtDeleted){
                node = node.next;
            }
            node.next = null;
            pToBtDeleted = null;
        }
    }

    public static void PrintListNode(ListNode pListHead){
        ListNode node = pListHead;
        while(node != null){
            if(node.next == null){
                System.out.print(node.value);
            }
            else{
                System.out.print(node.value + "->");
            }
            node = node.next;
        }
    }
}


//class ListNode{
//    int value;
//    ListNode next;
//}

/*
1->2->4->5
 */